package q31_nextPermutation;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
//        int[] nums = {5,2,5,8,6,1,4,5,9,2,7,4};
//        int[] nums = {1,2,7,9,6,5,4};
//        int[] nums = {1,3,2};
        int[] nums = {2, 3, 1};
        // int[] nums = {1,2,3,4,5,4,3,2,1};
//        int[] nums = {1,2};

        nextPermutation(nums);
        // BubbleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 此方法在第一个题解中有提到
     * 我们希望操作结束后的下一个数比当前这个数大，但是增加的幅度又要尽可能的小
     * 所以我们要从后向前查找
     */
    public static void nextPermutation(int[] nums) {
        if (nums.length == 1) {
            return;
        }
        // 用了两个指针
        // 分别指向倒数第一个和倒数第二个数字
        int left = nums.length - 2;
        int right = nums.length - 1;

        // 当指针没有走完时进行循环
        while (left >= 0) {
            // 如果left指针位置一直大于后面的数
            // 例如4321 则需要不断移动left向左
            if (nums[left] >= nums[left + 1]) {
                left--;
            } else {
                // 否则遇到了left指针位置小于它后面的数
                // 我们以123654为例
                // left指针将会走到3的位置
                // 那么此时应该更改3和4的位置
                // 于是得到了124653 但这并不是下一个字典序
                // 要得到字典序，我们应该将交换后4位置后面的数字都进行排序（从低到高）
                // 于是就得到了答案
                while (right > left) {
                    // 还有一个问题，就是要当right指针的数比left大才交换
                    // 像是127983 要交换7和8 而不是7和3
                    if (nums[left] >= nums[right]) {
                        right--;
                    } else {
                        break;
                    }
                }
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                // 这里使用了冒泡排序，使后面的数组变成升序，
                // 但实际上后面的数组一定是降序排列的
                BubbleSort(nums, left + 1);
                break;
            }


        }

        if (left == -1) {
            Arrays.sort(nums);
        }

    }

    public static void BubbleSort(int[] arr, int start) {
        for (int x = start; x < arr.length - 1; x++) {
            for (int y = start; y < arr.length - 1 - x + start; y++) {
                if (arr[y] > arr[y + 1]) {
                    int temp = arr[y];
                    arr[y] = arr[y + 1];
                    arr[y + 1] = temp;
                }
            }
        }
    }

}
